package com.itheima;


import com.sun.source.tree.Tree;

import java.util.*;

public class TreeProblem {

    public int maxDepth(TreeNode root) {
        int depth = 0;
        depth = getTreeDept(root, 0);
        return depth;
    }

    int getTreeDept(TreeNode treeNode, int dept) {
        if(treeNode == null) return dept;
        if(treeNode.left != null) {
            return Math.max(dept, getTreeDept(treeNode.left, dept + 1));
        }
        if(treeNode.right != null) {
            return Math.max(dept, getTreeDept(treeNode.right, dept + 1));
        }
        return dept;
    }

    public boolean isSymmetric(TreeNode root) {

        boolean res = isSymme(root.left, root.right);
        return res;
    }


    boolean isSymme(TreeNode ltree, TreeNode rtree) {
        if(ltree == null && rtree == null) return true;
        if(ltree == null || rtree == null) return false;


        return ltree.val == rtree.val &&  isSymme(ltree.left, rtree.right) && isSymme(ltree.right, rtree.left);
    }

    int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        ans = 0;
        topic543Sun(root);
        return ans - 1;
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        Deque<List<TreeNode>> s = new LinkedList<>(); //存储根节点并弹出

        List<List<Integer>> res = new ArrayList<>();
        List<TreeNode> tn = new ArrayList<>();
        tn.add(root);
        s.push(tn);
        while(!s.isEmpty()) {
            List<TreeNode> l = s.pop();
            List<Integer> list = new ArrayList<>();
            List<TreeNode> tr = new ArrayList<>();
            for(TreeNode node : l) {
                if(node != null) list.add(node.val);
                if(node.left != null) {
                    tr.add(node.left);
                }
                if(node.right != null) {
                    tr.add(node.right);
                }
            }

            if(!list.isEmpty())
                res.add(list);
            if(!tr.isEmpty())
                s.push(tr);
        }

        return res;
    }


    int topic543Sun(TreeNode root) {
        if(root == null) return 0;
        int left = topic543Sun(root.left);
        int right = topic543Sun(root.right);
        ans = Math.max(ans, Math.max(left, right) + 1);
        return Math.max(left, right) + 1;
    }

}

class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
}
